import java.util.*;


public class Algorithem {

	public static HashSet<Integer> SFT(int n, double tau, double delta, Function f) {
		int log2 = (int) Math.ceil(Math.log(n)/Math.log(2));
		int size = log2 + 2;
		HashSet<Integer>[] AtoB = new HashSet[size];
		HashSet<Integer> Q = new HashSet<Integer>();
		Map<Integer, Complex> QwithF;
		HashSet<Integer> L = new HashSet<Integer>();
		double cons = 1000; //TODO find the const
		double delta2 = Math.pow((Math.pow(f.getNorm(2, n), 2)/tau), 1.5)*log2;
		delta2 = delta/delta2;
		delta2 *= cons;
		AtoB = GQA(n, tau/36, f.getNormInfinity(), delta2, size);
		
		HashSet<Integer> minus = new HashSet<Integer>();
		for (int i=1; i<AtoB.length; i++) {
			minus.addAll(AtoB[i]);
		}
		for(int i: AtoB[0]) {
			for (int j: minus) {
				int num = modolu(i-j, n);
				Q.add(num);
			}
		}
		
		QwithF = applyF(Q, f);
		L = FixedQueries(n, tau, AtoB, QwithF, f);
		return L;
	}

	private static HashSet<Integer> FixedQueries(int n, double tau,
			HashSet<Integer>[] groups, Map<Integer, Complex> QF, Function f) {
		
		HashSet<HashSet<Integer>> candidate = new HashSet<HashSet<Integer>>();
		HashSet<HashSet<Integer>> nextCandidate;
		HashSet<Integer> start = new HashSet<Integer>();
		HashSet<Integer> temp1, temp2;
		HashSet<Integer> answer = new HashSet<Integer>();
		start.add(0);
		start.add(n-1);
		candidate.add(start);

		for(int i=0; i<groups.length-2; i++){
			nextCandidate = new HashSet<HashSet<Integer>>();
			for (HashSet<Integer> s : candidate) {
				int a = getMin(s);
				int b = getMax(s);
				int c = Math.round((a+b)/2);
				temp1 = new HashSet<Integer>();
				temp2 = new HashSet<Integer>();
				temp1.add(a);
				temp1.add(c);
				if (c+1 <= b) {
					temp2.add(c+1);
				}
				temp2.add(b);
				if (Distinguish(temp1, tau, groups[0], groups[i+1], QF, n)){
					nextCandidate.add(temp1);
				}
				if (Distinguish(temp2, tau, groups[0], groups[i+1], QF, n)) {
					nextCandidate.add(temp2);
				}
			}
			candidate.clear();
			candidate.addAll(nextCandidate);
		}
		
		for (HashSet<Integer> s : candidate){
			if (getMin(s) == getMax(s)) {
				if (Distinguish(s, tau, groups[0], groups[groups.length-1], QF, n)) {
					answer.add(getMin(s));
				}
			}
			else {
				temp1 = new HashSet<Integer>();
				temp1.add(getMin(s));
				temp2 = new HashSet<Integer>();
				temp2.add(getMax(s));
				if (Distinguish(temp1, tau, groups[0], groups[groups.length-1], QF, n)) {
					answer.add(getMin(s));
				}
				if (Distinguish(temp2, tau, groups[0], groups[groups.length-1], QF, n)) {
					answer.add(getMax(s));
				}
			}
		}
		return answer;
	}

	private static int getMax(HashSet<Integer> s) {
		int answer = Integer.MIN_VALUE;
		for (int i: s) {
			if (i>answer)
				answer=i;
		}
		return answer;
	}
	
	private static int getMin(HashSet<Integer> s) {
		int answer = Integer.MAX_VALUE;
		for (int i: s) {
			if (i<answer)
				answer=i;
		}
		return answer;
	}

	private static boolean Distinguish(HashSet<Integer> interval, double tau, HashSet<Integer> A, HashSet<Integer> B, Map<Integer, Complex> QF, int n) {
		double est=0;
		Complex sum;
		int a = getMin(interval);
		int b = getMax(interval);
		double middle = Math.floor((a+b)/2);
		for(int x: A) {
			sum = new Complex();
			for (int y : B) {
				Complex kay = Complex.Chi(middle, y, n);
				int var = modolu(x-y, n);
				sum.add(Complex.divScalar(Complex.multNew(kay,QF.get(var)),(double)B.size()));
			}
			est += (Complex.norm2(sum))/((double)A.size());
		}
		if(tau*5/36<=est)
			return true;
		else
			return false;
	}
	
	private static Map<Integer, Complex> applyF(HashSet<Integer> q, Function f) {
		Map<Integer, Complex> answer = new HashMap<Integer, Complex>();
		for (int i: q) {
			answer.put(i, f.getVal(i));
		}
		return answer;
	}

	private static HashSet<Integer>[] GQA(int n, double gamma, double norm, double delta, int size) {
		double ca = 0.302; //TODO find the const
		double cb = 0.01000003;
		int ma = (int) (ca*(Math.log(1.0/delta))*(1.0/(gamma*gamma)));
		int mb = (int) (cb*(Math.log(1.0/(delta*gamma)))*(1.0/(gamma*gamma)));
		HashSet<Integer>[] answer = new HashSet[size];
		ma = modolu(ma, n);
		mb = modolu(mb, n);
		answer[0] = Function.genRandSet(ma, n);
		int elements = 1;
		for (int l=1; l<size - 1; l++) {
			answer[l] = Function.genRandSet(Math.min(mb, elements), elements);
			elements*=2;
		}
		int log2 = mylog(n,2);
		int m = (int) Math.pow(2, log2);
		answer[size-1] = Function.genRandSet(Math.min(Math.min(m, n), mb), n);
		
		return answer;
	}
	
	public static int mylog(int num, int base) {
		double answer = Math.log(num)/Math.log(base);
		return (int)answer + 1;
	}
	
	public static int modolu(int num, int mod) {
		int n = num%mod;
		if (n<0){
			n+=mod;
		}
		return n;
	}
}
